\documentclass[fleqn,10pt]{article}
\usepackage{graphicx} % Required for inserting images
\usepackage{xeCJK} 
\usepackage{amsmath}
\usepackage{pgfplots}
\usepackage{subcaption}
\usepackage{listings}
\usepackage{mdframed}
\usepackage[dvipsnames]{xcolor}

\title{Homework03  Report  of  D.S.A.\\{硬币找零问题}}
\author{3220101611  韩耀霆}
\date{\today}

\begin{document}
\flushbottom
\maketitle
\tableofcontents

\section{项目任务}  
课本提供的 code 当中(可以在群文件中下载), 已经提供了 \verb|BinarySearchTree.h| , \verb|AvlTree.h|, \verb|RedBlackTree.h| 和 \verb|SplayTree.h|, 分别实现了对应的功能. 由于是教学代码, 每一个头文件都是独立的. 现在, 请根据它们各自的用途, 整理它们的逻辑关系, 重构全部代码, 并用继承关系予以表达. 要求:

\section{处理思路}
\subsection{顶级基类的创建}
\subsubsection{\verb|BinaryTree|的类模板}
参考讲义中给出的HINT，我们建立了名为\verb|BinaryTree|的顶级基类，其中主要包括三个遍历函数和二叉树中必要的部分纯虚函数，提供了一个基本的二叉树接口，具体实现由派生类完成。通过继承这个类模板并实现相应的函数，可以创建不同类型的二叉树，如二叉搜索树、平衡二叉树等。其具体介绍和代码如下：

\begin{itemize}
    \item 遍历函数：
        \begin{itemize}
            \item \verb|Preorder_Traversal()|：前序遍历二叉树。
            \item \verb|Inorder_Traversal()|：中序遍历二叉树。
            \item \verb|Postorder_Traversal()|：后序遍历二叉树。
        \end{itemize}
    \item 纯虚函数：
        \begin{itemize}
            \item \verb|isEmpty()|：判断树是否为空。
            \item \verb|makeEmpty()|：清空树。
            \item \verb|insert(const Comparable &x)|：向树中插入元素x。
            \item \verb|remove(const Comparable &x)|：从树中移除元素x。
        \end{itemize}
\end{itemize}

\begin{lstlisting}[language=C++, numbers=left, numbersep=2em, basicstyle=\ttfamily, breaklines=true]
template <typename Comparable>
class BinaryTree
{
    public:

    void Preorder_Traversal() const;

    void Inorder_Traversal() const;

    void Postorder_Traversal() const;

    virtual bool isEmpty() const = 0;

    virtual void makeEmpty() = 0;

    virtual void insert(const Comparable &x) = 0;

    virtual void remove(const Comparable &x) = 0;
};
\end{lstlisting}

\subsubsection{\verb|Node|的结构体模板}
依照项目要求中给出的考虑各种 Node 之间的关系和结构，我们给出Node的结构体模板来做统一规划，额外的，由于\verb|SPlayTree|的特殊性，我们在这里确保Node类有无参数的构造函数，其具体代码如下：
  
\begin{lstlisting}[language=C++, numbers=left, numbersep=2em, basicstyle=\ttfamily, breaklines=true]
template <typename Comparable>
struct Node
{
    Comparable element;

    Node ( const Comparable & ele)
        : element(ele) { }
    Node() {}
};
\end{lstlisting}

\subsection{继承关系的处理}
这里指描述处理一些特殊问题的思路与方法，平凡的继承在这里不做特殊强调。\\
\begin{itemize}
    \item 模板声明的问题，为了使程序可以在private部分检测到模板的同时避免多次声明的问题，我们引入了新的模板名以解决这类问题；
    \item 函数Node的修改，这里的操作也比较简单，就是加上模板名就好；
    \item 虽然可能有些无聊，但是为了避免递归操作产生的一些不必要的溢出，我们将代码中给出了非递归做法的部分进行了替换。
\end{itemize}

\section{测试文件}  
测试文件由原本的四个文件各自单独作为函数，统一修改了部分输入与输出，这里没什么可以说的。 

\section{总结与部分阐释}
其实整体而言不是特别难，但确实是少有的读这么老长的代码（），浅浅吐槽一下这个教学代码用的乱乱的，递归和迭代混着用可还行（），还有就是红黑树的remove操作在教学代码中并未给出，我注在了最后，但是考虑到实现问题和debug问题，并未实际引入，如果想带上的话，只需要将remove的函数做替换就好了（）。

\end{document}
